package 动态规划;

/**
 * @ClassName: Hanoi
 * @Description: 汉诺塔
 * @author: WangZe
 * @date: 2022/3/14 13:35
 */
public class Hanoi {
    /**
     * 汉诺塔问题，每次只能移动一个，不能改变顺序
     */
    public static void main(String[] args) {
        Hanoi hanoi = new Hanoi();
        String p1 = "柱子A";
        String p2 = "柱子B";
        String p3 = "柱子C";
        hanoi.solution(3,p1,p2,p3);
    }

    /**
     * 当n == 1 ，可以直接从 A 移动到 C
     * 当n > 1，可以拆分中散步
     *  1.将n-1个盘子从 A 移动到 B
     *  2.将编号为 n的盘子 从 A 移动到C
     *  3.将n-1 个盘子从B移动到C
     * @param n
     * @param p1
     * @param p2
     * @param p3
     * 将n个盘子 从p1柱子移动到p3柱子
     */
    public void solution(int n,String p1,String p2,String p3){
        if(n == 1){
            move(n,p1,p3);
            return;
        }
        //1.将n-1个盘子从 A 移动到 B
        solution(n-1,p1,p3,p2);
        //2.将编号为 n的盘子 从 A 移动到C
        move(n,p1,p3);
        //3.将n-1 个盘子从B移动到C
        solution(n-1,p2,p1,p3);
    }
    void move(int no,String from,String to){
        System.out.println("将"+no+" 盘子"+"从 "+from+"移动到"+to);
    }
}
